package com.cet.algorithm.字符串;

/**
 * @program: algorithm
 * @description: 字符串是否能够由重复字串构成
 * @author: 陈恩涛
 * @create: 2022-03-22 14:46
 **/
public class LC459 {

    /**
     *
     * @param s
     * @return
     */
    public static boolean repeatedSubstringPattern(String s) {
        int[] next = new int[s.length()];
        getNext(next, s);
        if (next[s.length()-1] > 0 && s.length() % (s.length() - next[s.length() - 1]) == 0) {
            return true;
        } else {
            return false;
        }
    }

    public static void getNext(int[] next, String patten) {
        int j = 0;
        next[0] = 0;
        for (int i = 1; i < patten.length(); i++) {
            // 前后缀最后一个元素不等时
            while (j > 0 && patten.charAt(i) != patten.charAt(j)) {
                j = next[j - 1];
            }
            // 前后缀最后一个元素相等时
            if (patten.charAt(i) == patten.charAt(j)) {
                j++;
            }
            next[i] = j;
        }
    }

    public static void main(String[] args) {
        System.out.println(repeatedSubstringPattern("abcdabcdabcdabcd"));
    }
}
